package cn.cmvideo.springboot.algorithm;

import java.util.Arrays;

/**
 * 数组全排列(无重复数字)<br>
 * 1、数组排序<br>
 * 2、从右往左找第一个逆序的数组，记录下标为index。若这个数组完全逆序，则表示已经输出完毕，退出<br>
 * 3、从有往左找第一个比array[index]大的数，然后交换这个数和index处的值，将array数组中从index+1下标处开始的之后的数进行逆序排序<br>
 * @author Administrator
 *
 */
public class Arrangement
{

	public static void permute(int[] array, int start)
	{
		Arrays.sort(array);
		int index = 0;
		long factorial = factorial(array.length);
		long f = 0l;
		while (f < factorial)
		{
			f++;
			printArray(array);

			for (int i = array.length - 2; i >= 0; i--)
			{
				if (array[i] < array[i + 1])
				{
					index = i;
					break;
				} else if (i < 0)
				{
					return;
				}
			}

			for (int i = array.length - 1; i >= 0; i--)
			{
				if (array[i] > array[index])
				{
					// 交换
					swap(array, i, index);
					break;
				}
			}

			reverse(array, index + 1);
		}

	}

	public static void reverse(int array[], int i)
	{
		int k = i;
		int j = array.length - 1;
		while (k < j)
		{
			swap(array, k, j);
			k++;
			j--;
		}
	}

	public static void swap(int[] array, int s, int i)
	{
		int temp = array[s];
		array[s] = array[i];
		array[i] = temp;
	}

	public static void printArray(int[] array)
	{
		for (int i = 0; i < array.length; i++)
		{
			System.out.print(array[i]);
		}
		System.out.print("\n");
	}

	public static long factorial(int n)
	{
		long sum = 1l;
		if (n > 0)
		{
			for (int i = 1; i <= n; i++)
			{
				sum = sum * i;
			}
		}
		return sum;
	}

	public static void main(String[] args)
	{
		int[] array = new int[] { 1, 3, 2, 4 };
		permute(array, 0);
	}

}
